/*
提交链接：https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/submissions/572341233
600. 不含连续1的非负整数-困难
完成日期：2024/10/13
数位DP
*/

class Solution {
public:
    int findIntegers(int n) {
        // 将 n 转换为二进制字符串
        string binary = bitset<32>(n).to_string(); // 处理32位整数
        int length = binary.length();
        // dp[i] 表示 i 位数中没有连续 1 的有效数的个数
        vector<int> dp(length + 1);
        dp[0] = 1; // dp[0] = 1 表示 0 位数，只有一个数 0
        dp[1] = 2; // dp[1] = 2 表示 1 位数，有 0 和 1
        for (int i = 2; i <= length; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        int count = 0; // 统计符合条件的数
        for (int i = length - 1; i >= 0; --i) {
            if (binary[length - 1 - i] == '1') {
                count += dp[i]; 
                if (i < length - 1 && binary[length - 1 - (i + 1)] == '1') {
                    break; // 如果连续出现 1，则终止
                }
            }
            // 到达最后一位后，如果没有连续 1，就加 1
            if (i == 0) {
                count++; // 包含 n 本身
            }
        }
        return count;
    }
};